#
# @lc app=leetcode.cn id=42 lang=python3
#
# [42] 接雨水
#
from typing import List

"""
前后缀的方法中，将前后缀最大值分别存储到了不同的数组中，但在最后计算结果的时候其实只使用了 i 位置的值
所以可以用两个变量来代替原本的前后缀数组，用双指针来遍历 height 数组
灵神的方法中，双指针循环是将 left, right = 0, n-1，循环条件为 left < right，在 height 数组只有两个值时依然会循环一次，但实际上这样的数组的结果一定是0无需计算
在我的理解中，数组的首尾柱子一定是无法接到雨水的，所以无需计算，仅计算内部的 n-2 个柱子，
所以 left, right = 1, n-2 ，left <= right，这样循环次数较灵神的方法减少了一次，而且对于我个人来说更能够理解一些
"""
# @lc code=start

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        
        pre_max = height[0]
        suf_max = height[-1]
        
        left, right = 1, n-2
        res = 0
        
        while left <= right:
            print(left, right)
            pre_max = max(pre_max, height[left])
            suf_max = max(suf_max, height[right])
            
            if pre_max < suf_max:
                res += pre_max - height[left]
                left += 1
            else:
                res += suf_max - height[right]
                right -= 1
                
        return res
# @lc code=end

print(Solution.trap(Solution, [2,1,1,3]))